
package com.liwt.algorithm;

import java.util.Stack;

/**
 * 用两个堆栈模拟队列的操作（入队与出队）。
 * 
 * @author likebamboo
 * @create 2013-10-21
 * @see http://blog.csdn.net/likebamboo/article/details/12904777
 * @param <E>
 */
public class MyQueue<E> {

    /**
     * A栈
     */
    private Stack<E> stackA;

    /**
     * B栈
     */
    private Stack<E> stackB;

    public MyQueue() {
        super();
        stackA = new Stack<E>();
        stackB = new Stack<E>();
    }

    /**
     * 出队操作
     * 
     * @return
     */
    public E poll() {
        // 如果A栈为空，那么返回B栈的栈顶元素
        if (stackA.isEmpty()) {
            return stackB.pop();
        }
        // 如果A栈不为空，首先将A栈的元素压入B栈
        while (!stackA.isEmpty()) {
            stackB.push(stackA.pop());
        }
        return stackB.pop();
    }

    /**
     * 入队列操作
     * 
     * @param item
     */
    public void offer(E item) {
        // 如果栈B为空，直接压入A栈
        if (stackB.isEmpty()) {
            stackA.push(item);
            return;
        }
        // 如果栈B不为空，首先将栈B中的元素压入A中。
        while (!stackB.isEmpty()) {
            stackA.push(stackB.pop());
        }
        stackA.push(item);
    }

    /**
     * 判断队列是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return stackA.isEmpty() && stackB.isEmpty();
    }

    public static void main(String[] args) {
        MyQueue<String> q = new MyQueue<String>();

        boolean isEmpty = q.isEmpty();
        if (isEmpty) {
            q.offer("the first str");
            q.offer("the second str");
            System.out.println(q.poll());
            q.offer("the third str");
            System.out.println(q.poll());
            q.offer("the forth str");
            q.offer("the fifth str");
            System.out.println(q.poll());
            System.out.println(q.poll());
        }
    }
}
